Many search engines provide query suggestion functionality in which a user, having entered a particular search query, is given a set of suggested queries related to the user's search query. These related queries may be helpful if the search results of the user's search query do not contain the information the user was seeking and one of the related queries will provide useful search results. The user may select one of the related queries causing a search to be performed using the selected query and search results to be returned to the user. In some cases, related queries may be useful even when users find what they were looking for by getting the users interested in other topics to explore.
A variety of different approaches and algorithms have been employed for determining related queries for a given search query. For instance, related queries may be suggested that have a short edit distance from the given search query or that contain similar words. Another approach suggests related queries based on terms occurring in the search result documents for the given search query. Further approaches suggest related queries based on the similarity of result documents between search queries.
However, a common problem for the various approaches is determining related queries that are relevant and useful. For instance, suppose that a search query is “Tom Cruise.” Based on this search query, “Katie Holmes” would most likely be a relevant related query as people searching for documents associated with “Tom Cruise” are likely to be interested in information associated with “Katie Holmes.” Alternatively, “Dream Cruise” would most likely be an irrelevant related query as people searching for documents associated with “Tom Cruise” are most likely not searching for information on seagoing holidays.